package ms;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

public class Q2 {
    class Node {
        int val;
        Node left;
        Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    int maxDepth;
    //    int offset;
    HashMap<Integer, Integer> depthOffsetMap = new HashMap<>();

    public int findDepth(String serializedTree) {
        if (serializedTree == null || serializedTree.length() == 0) {
            return maxDepth;
        }
        preOrder(serializedTree, 0, 1, 0);
        return maxDepth;
    }

    public void preOrder(String serializedTree, int index, int depth, int offset) {
        if (index > serializedTree.length() - 1) {
            maxDepth = Math.max(maxDepth, depth - 1);
            return;
        }
        if (serializedTree.charAt(index) == 'L') {
            maxDepth = Math.max(maxDepth, depth);
//            offset += 2;
            depthOffsetMap.put(depth, depthOffsetMap.getOrDefault(depth, getOffsetByDepth(depth)) + 2);
            updateDeperOffset(depth);
            return;
        }
        int left = serializedTree.charAt(index) == 'N' ? 2 * index + 1 - getOffsetByDepth(depth) : 2 * index + 1;
        // The index will be switched back by an offset due to the accumulative Leaves met in the current level
        int right = serializedTree.charAt(index) == 'N' ? 2 * index + 2 - getOffsetByDepth(depth) : 2 * index + 2;
        preOrder(serializedTree, left, depth + 1, offset);
        preOrder(serializedTree, right, depth + 1, offset);
    }

    public int getOffsetByDepth(int depth) {
        while (depth > 0 && !depthOffsetMap.containsKey(depth)) {
            depth--;
        }
        return depthOffsetMap.getOrDefault(depth, 0);
    }

    public void updateDeperOffset(int depth) {
        while (depthOffsetMap.containsKey(++depth)) {
            depthOffsetMap.put(depth, depthOffsetMap.get(depth) + 2);
        }
    }

    /**
     * Another attemp to solve the problem by directly build the tree and then find its depth
     */

    public int findDepthByLevelTraverse(String serializedTree) {
        if (serializedTree.length() == 0) {
            return 0;
        }
        int depth = 0, index = 0;
        Queue<Character> queue = new LinkedList<>();
        queue.add(serializedTree.charAt(0));
        while (!queue.isEmpty()) {
            int noPerlevel = queue.size();
            for (int i = 0; i < noPerlevel; i++) {
                char c = queue.remove();
                if (c != 'L') {
                    queue.add(serializedTree.charAt(++index));//add left child
                    if(index >= serializedTree.length() - 1){
                        break;
                    }// in case the node only have one child
                    queue.add(serializedTree.charAt(++index));//add right child
                }
            }
            depth++;
        }
        return depth;
    }

    public static void main(String[] args) {
        System.out.println("Answers bny level traverse:");
        System.out.println(new Q2().findDepthByLevelTraverse("NLL"));
        System.out.println(new Q2().findDepthByLevelTraverse("NNNLLL"));
        System.out.println(new Q2().findDepthByLevelTraverse("NLNLL"));
        System.out.println(new Q2().findDepthByLevelTraverse("NNLLL"));
        System.out.println(new Q2().findDepthByLevelTraverse("NLNLNLL"));
        System.out.println(new Q2().findDepthByLevelTraverse("NNNLLLNLL"));
        System.out.println(new Q2().findDepthByLevelTraverse("NLNNNLLLNLL"));
        System.out.println(new Q2().findDepthByLevelTraverse("NNNLNLNLLLNLNLL"));

        System.out.println("Answers by preOrder DFS");
        System.out.println(new Q2().findDepth("NLL"));
        System.out.println(new Q2().findDepth("NNNLLL"));
        System.out.println(new Q2().findDepth("NLNLL"));
        System.out.println(new Q2().findDepth("NNLLL"));
        System.out.println(new Q2().findDepth("NLNLNLL"));
        System.out.println(new Q2().findDepth("NNNLLLNLL"));
        System.out.println(new Q2().findDepth("NLNNNLLLNLL"));
        System.out.println(new Q2().findDepth("NNNLNLNLLLNLNLL"));
    }
}
